package com.hyb.algorithm.data.struct.tree;

/**
 * @Author: huyanbing
 * @Date: 2021/9/3 6:38 下午
 */
public class DeleteNode {

    public static void main(String[] args) {

    }

    public TreeNode deleteNode(TreeNode root, int target) {

        if (root == null) {
            return null;
        }

        if (root.val == target) {

            //如果两个节点都是空
            if (root.left == null) {
                return root.right;
            }

            if (root.right == null) {
                return root.left;
            }

            //找到右子树 的最小节点， 左子树的最大值
            TreeNode minRoot = getMin(root.right);

            root.val = minRoot.val;

            root.right = deleteNode(root.right, minRoot.val);
        } else if (root.val > target) {
            return deleteNode(root.left, target);
        } else {
            return deleteNode(root.right, target);
        }

        return null;
    }

    /**
     * 寻找最小值
     *
     * @param root
     * @return
     */
    private TreeNode getMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }

        return root;
    }
}
